Bài toán đơn giản nhất và thông dụng nhất cho luồng trên mạng là bài toán tìm luồng cực đại trong một đồ thị cho trước, với kết quả mong muốn là luồng tổng lớn nhất có thể từ điểm nguồn đến điểm thu. Có nhiều bài toán khác có thể được giải bằng các thuật toán luồng cực đại, nếu chúng được mô hình hóa dưới dạng các mạng vận tải, chẳng hạn như các bài cặp ghép hai phía, bài toán phân công công việc (assignment problem), bài toán vận tải.

Trong một bài toán luồng đa (multi-commodity flow problem), ta có nhiều điểm phát, nhiều điểm thu, và nhiều loại "hàng" cần chảy từ một nút phát cho trước tới một nút thu cho trước. Ví du, nhiều loại hàng được sản xuất tại nhiều nhà máy, và cần được chuyên chở đến cho các khách hàng khác nhau qua cùng một mạng giao thông.

Trong một bài toán luồng chi phí cực tiểu, mỗi cung u , v {\displaystyle u,v} có một chi phí cho trước k ( u , v ) {\displaystyle k(u,v)} , và chi phí gửi luồng f ( u , v ) {\displaystyle f(u,v)} qua cung đó là f ( u , v ) ⋅ k ( u , v ) {\displaystyle f(u,v)\cdot k(u,v)} . Mục tiêu là gửi một luồng có dung lượng cho trước từ nguồn tới điểm thu với chi phí thấp nhất.

Trong một bài toán luồng tuần hoàn (circulation problem), với mỗi cung ( u , v ) {\displaystyle (u,v)} , ngoài c ( u , v ) {\displaystyle c(u,v)} còn có một cận dưới l ( u , v ) {\displaystyle l(u,v)} . Mỗi cung cũng có một chi phí. Thông thường, trong bài toán luồng tuần hoàn, điều kiện cân bằng luồng sẽ phải áp dụng cho mọi nút, và có một kết nối giữa điểm thu ngược trở lại điểm phát. Bằng cách này, ta có thể áp đặt luồng tổng bằng l ( t , s ) {\displaystyle l(t,s)} và c ( t , s ) {\displaystyle c(t,s)} . Do luồng tuần hoàn trong mạng nên bài toán được đặt tên như vậy.

Mối quan hệ giữa các bài toán luồng

Nhiều biến thể của các bài toán luồng có quan hệ với nhau với hình thức bài này là tổng quát hóa hay chuyên biệt hóa của bài kia. Trong cây dưới đây, một bài toán có thể được giải bằng một lời giải cho bài toán cha.

• Bài toán luồng với các điều kiện và hàm mục tiêu tùy ý.
  • Bài toán luồng với các điều kiện tuyến tính.
    • Bài toán luồng tuần hoàn đa (Multi-commodity circulation problem). Thuật toán thời gian đa thức duy nhất được biết là giải bằng quy hoạch tuyến tính.
      • Bài toán luồng đa chi phí cực tiểu. Đặt tất cả các cận dưới bằng 0.
        • Bài toán luồng chi phí cực tiểu. Giải với một loại hàng, 1 thu, 1 phát.
          • Bài toán luồng cực đại. Đặt tất cả chi phí bằng 0 và cực đại hóa luồng.
          • Bài toán tìm một đường đi ngắn nhất. Đặt tất cả các khả năng thông qua bằng 1, tìm luồng có độ lớn 1.
        • Bài toán luồng đa. Đặt tất cả chi phí bằng 0.
          • Đặt tất cả chi phí bằng 0. Giải với một loại hàng, 1 thu, 1 phát.
        • Bài toán tìm đường đi ngắn nhất cho mọi cặp đỉnh. Cho các khả năng thông qua là vô hạn, tìm luồng độ lớn 1 cho v ( v − 1 ) / 2 {\displaystyle v(v-1)/2} loại hàng, mỗi loại cho 1 cặp đỉnh.
      • Bài toán luồng tuần hoàn. Giải với một loại hàng, 1 thu, 1 phát.

Trong tất cả các bài toán trên, ta có thể tìm một luồng cực đại hoặc một luồng có độ lớn cho trước.